# 47/100 二叉树-从前序与中序遍历序列构造二叉树(好题)
# leetcode第105题: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/1/6
from typing import Optional

from leetcode.bds import TreeNode, TreeConverter
import leetcode.test as test

"""通过前序和中序确定树的结构
首先根据前序遍历的第一个节点确定为root, 在中序遍历中找到root节点, root的左侧为左子树, root的右侧为右子树
然后再根据前序来确定左子树的根节点root_l, 和右子树的根节点root_r, 用这样的方法递归, 即可构造出树的结构
"""


def build_tree_rec(preorder: list[int], inorder: list[int]):
    """使用递归的方法"""

    def build_tree(pre_order, in_order):
        if not pre_order or not in_order:
            return None

        # 前序遍历的第一个节点是根节点
        root_val = pre_order[0]
        root = TreeNode(root_val)

        # 在中序遍历中找到根节点的位置
        root_index = in_order.index(root_val)

        # 分割左右子树
        left_inorder = in_order[:root_index]
        right_inorder = in_order[root_index + 1:]

        left_preorder = pre_order[1:1 + len(left_inorder)]
        right_preorder = pre_order[1 + len(left_inorder):]

        # 递归构造左右子树
        root.left = build_tree(left_preorder, left_inorder)
        root.right = build_tree(right_preorder, right_inorder)
        return root

    root = build_tree(preorder, inorder)
    return TreeConverter.tree_to_list(root)


def build_tree_rec_opt(preorder: list[int], inorder: list[int]):
    """优化递归方法, 构建了一个映射"""

    def build_tree(rt, left, right):
        if left > right:
            return
        node = TreeNode(preorder[rt])
        i = mapping[preorder[rt]]
        node.left = build_tree(rt + 1, left, i - 1)
        node.right = build_tree(i - left + rt + 1, i + 1, right)
        return node

    mapping, preorder = {}, preorder
    for i in range(len(inorder)):  # 构建一个反向的映射, 避免频繁检索
        mapping[inorder[i]] = i
    root = build_tree(0, 0, len(inorder) - 1)
    return TreeConverter.tree_to_list(root)


def build_tree_stack(preorder: list[int], inorder: list[int]):
    """使用栈来实现
    对于前序遍历中的任意两个连续节点 u 和 v，根据前序遍历的流程，我们可以知道 u 和 v 只有两种可能的关系：
    1. v 是 u 的左儿子。这是因为在遍历到 u 之后，下一个遍历的节点就是 u 的左儿子，即 v；
    2. u 没有左儿子，并且 v 是 u 的某个祖先节点（或者 u 本身）的右儿子。如果 u 没有左儿子，那么下一个遍历的节点就是 u 的右儿子。
       如果 u 没有右儿子，我们就会向上回溯，直到遇到第一个有右儿子（且 u 不在它的右儿子的子树中）的节点 u a，那么 v 就是 u a的右儿子。

    流程为:
    1. 遍历前序序列，每次创建一个新节点。
    2. 如果栈顶节点的值不等于中序当前值，则新节点是栈顶节点的左子节点。
    3. 否则，根据中序遍历的顺序弹出栈顶节点，找到合适的父节点后，将新节点设为右子节点。
    """
    if not preorder or not inorder:
        return None

    root = TreeNode(preorder[0])  # 根节点是前序遍历的第一个值
    stack = [root]
    inorder_index = 0  # 用于跟踪中序遍历的位置

    for i in range(1, len(preorder)):
        node = TreeNode(preorder[i])  # 当前前序遍历节点值
        parent = stack[-1]  # 栈顶元素是当前节点的父节点

        # 如果栈顶元素不等于当前中序遍历的值，说明是左子树。
        if stack[-1].val != inorder[inorder_index]:
            parent.left = node
        else:
            # 向上回溯，直到找到第一个与中序遍历值不同的节点
            while stack and stack[-1].val == inorder[inorder_index]:
                parent = stack.pop()
                inorder_index += 1
            # 当前节点是右子树
            parent.right = node

        stack.append(node)

    return TreeConverter.tree_to_list(root)


if __name__ == '__main__':
    t_arr = [6, 4, 9, 2, 5, 7, 10, 1, 3, None, None, None, 8, ]
    root1 = TreeConverter.list_to_tree(t_arr)
    # TreeConverter.draw_tree_from_root(root1)

    inp = [{"preorder": [3, 9, 20, 15, 7], "inorder": [9, 3, 15, 20, 7]},
           {"preorder": [-1], "inorder": [-1]},
           {"preorder": [1, 2, 3], "inorder": [1, 2, 3]},
           {"preorder": [6, 4, 2, 1, 3, 5, 9, 7, 8, 10], "inorder": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]}, ]
    out = [[3, 9, 20, None, None, 15, 7], [-1], [1, None, 2, None, 3], t_arr, ]
    test.test_function(build_tree_rec, inp, out)
    test.test_function(build_tree_rec_opt, inp, out)
    test.test_function(build_tree_stack, inp, out)
